package data_structure.offer;

import java.util.ArrayList;

public class Binary {

    public static int numberOfBinary1(int n) {

        int count = 0;
        while (n != 0) {
            count++;
            n = (n - 1) & n;
        }

        return count;
    }


    public static double Power(double base, int n) {//对于浮点型数据和整形数据之间的判断是否相等，不能直接使用equal函数

        if (equal(base, 0)) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }
        double result = 0;
        if (n > 0) {
            result = multiply(base, n);
        } else {
            result = multiply(1 / base, -n);
        }
        return result;
    }

    public static double multiply(double base, int n) {

        double result = 1;
        for (int i = 0; i < n; i++) {
            result *= base;
        }
        return result;
    }

    public static boolean equal(double a, int b) {

        if (a - b > -0.000001 && a - b < 0.000001) {
            return true;
        } else {
            return false;
        }
    }

    static int results[];

    public static void printToMaxOfNDigits(int n) {
        results = new int[(int) (Math.pow((double) 10, (double) n)) - 1];
        int[] array = new int[n];
        if (n <= 0)
            return;
        printArray(array, 0);
    }

    //打印出来的并不真正的数字
    private static void printArray(int[] array, int n) {

        for (int i = 0; i < 10; i++) {

            if (n != array.length) {
                array[n] = i;
                printArray(array, n + 1);
            } else {
                boolean isFirstNo0 = false;
                int[] result = new int[array.length];
                for (int j = 0; j < array.length; j++) {
                    if (array[j] != 0) {
                        result[j] = array[j];
                        if (!isFirstNo0)
                            isFirstNo0 = true;
                    } else {
                        if (isFirstNo0)
                            result[j] = array[j];
                    }
                }
                int number = 0;
                int length = result.length - 1;
                for (int m = 0; m < result.length; m++) {
                    int dix = length - m;
                    number = number + (int) (Math.pow((double) 10, (double) dix)) * result[m];
                }
                if (number > 0) {
                    results[number - 1] = number;
                }
                return;
            }
        }
    }

    public static int[] getResults() {
        return results;
    }

    public static void reOrderArray(int array[]) {

        if (array == null || array.length == 0) {
            return;
        }

        int left = 0;
        int right = array.length - 1;
        while (left < right) {

            while (left < right && array[left] % 2 == 0) {
                left++;
            }
            while (left < right && array[right] % 2 != 0) {
                right--;
            }
            if (left < right) {
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }
    }

    public static ArrayList<Integer> spiralOrder(int[][] matrix) {

        ArrayList<Integer> result = new ArrayList<Integer>();

        int r1 = 0, r2 = matrix.length - 1;
        int c1 = 0, c2 = matrix[0].length - 1;

        while (r1 <= r2 && c1 <= c2) {
            //from the left to right
            for (int c = c1; c <= c2; c++) {

                result.add(matrix[r1][c]);
            }
            //from top to bottom
            for (int r = r1; r <= r2; r++) {
                result.add(matrix[r][c2]);
            }
            if (r1 < r2 && c1 < c2) {
                //from right to left
                for (int c = c2 - 1; c > c1; c--) {
                    result.add(matrix[r2][c]);
                }
                //from bottom to top
                for (int r = r2; r > r1; r--) {
                    result.add(matrix[r][c1]);
                }
            }
            c1++;
            c2--;
            r1++;
            r2--;
        }
        return result;
    }

    public ArrayList<String> permutation(String str){
        if(str==null||str.length()==0){
            return null;
        }
        ArrayList<String> result=new ArrayList<String> ();
        helper(result,0,str.toCharArray());
        return result;
    }

    private void helper(ArrayList<String> result, int index,char [] s){

        if(index==s.length-1){
            result.add(String.valueOf(s));
            return;
        }

        for(int i = index; i < s.length; i++){

            if(i==index||s[i]!=s[index]){
                swap(s,index,i);
                helper(result, index+1, s);
                swap(s,index,i);
            }
        }
    }
    private void swap(char [] s,int index,int i){

        char temp=s[i];
        s[i]=s[index];
        s[index] = temp;
    }



    public static void main(String[] args) {
        printToMaxOfNDigits(2);
        getResults();
        for (int value : getResults()) {

            System.out.println(value);
        }
    }


}
